1181번 단어 정렬

Day 14 13단계 20231108

첫 코드 처리 시간이 너무 길어서 문제를 푼 이후에 다른 사람들의 코드를 보고 수정하면서 수정된 코드별 속도를 비교해봤다.

코드번호	메모리	코드길이	처리시간	배열종류	비교방법	출력방법
1번	26300 KB	736 B	1820 ms	ArrayList	length() 차이, charAt() 비교	System.out.println()
2번	25448 KB	616 B	2084 ms	ArrayList	length() 차이, compareTo()	System.out.println()
3번	28244 KB	844 B	1584 ms	ArrayList	length() 차이, charAt() 비교	System.out.println(sb.toString())
4번	28084 KB	953 B	396 ms	String[]	length() 차이, charAt() 비교	System.out.println(sb.toString())
5번	28716 KB	804 B	368 ms	String[]	length() 차이, compareTo()	System.out.println(sb.toString())
6번	29560 KB	977 B	388 ms	String[]	length() 차이, compareTo()	br.write(sb.toString())
7번	22640 KB	906 B	352 ms	String[]	length() 차이, compareTo()	br.write(strArr[i])

결론
7번 코드 : String[]으로 저장하고, compareTo()로 문자열을 비교하고, BufferedWriter의 write()메소드를 사용해서 출력한 것의 처리 시간이 가장 짧았다.
코드 길이는 6번 코드가 가장 길었고(길이 977 B, 처리시간 388 ms), 2번 코드가 가장 짧았다.(길이 616 B, 처리시간 2084 ms)
- 코드 길이와 처리 시간은 무조건 비례하지 않는다.
ArrayList를 사용했을 때가 String[]를 사용했을 때보다 처리 시간이 오래 걸렸다. 아마 같은 정렬 Comparator를 사용해도 내부 처리 과정으로 인한 차이가 있는 듯 보인다.
- 많은 양의 데이터를 배열에 넣어 정렬할 때 가변 배열인 List보다 속도 처리상으론 불변 배열을 쓰는 것 좋을 수 있다.
배열 요소를 System.out.print()로 일일이 출력하는 것보다 StringBuilder에 일일이 추가하는 것이, StringBuilder보다 BufferedWriter에 일일이 추가하는 것이 더 빠르다.

1번. 내 첫 풀이 코드

BufferedReader로 입력을 읽어온 이후, ArrayList<String>에 넣는다.
list를 sort()하는데 만약 두 문자열의 길이가 다르면 그 차이를 반환(11650번 좌표 정렬하기 참고)
길이가 같다면 String의 첫번째부터 각각 비교해서 같은지 확인하고, 다르다면 그 차이를 반환
위 과정으로 양수가 나온 경우들은 배열 순서를 교체, 음수(이 문제에선 중복을 제거했다)가 나오면 교체가 없다.
결과값을 System.out.print()로 배열의 모든 요소를 1개씩 출력한다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		List<String> list = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			String str = br.readLine();
			if (!list.contains(str)) list.add(str);
		}
		
		list.sort((s1, s2) -> {
			if (s1.length() != s2.length()) return s1.length() - s2.length();
			else {
				for (int i = 0; i < s1.length(); i++) {
				 if (s1.charAt(i) != s2.charAt(i)) 
					 return s1.charAt(i) - s2.charAt(i);
				}
			}
			return s1.length() - s2.length();
		});
		
		for(String s : list) System.out.println(s); 
	}
}

2번. 1차 수정코드

배열 종류는 ArrayList<String>을 사용했다.
비교 방법을 charAt() 비교에서 String.compareTo(s)로 바꿨다.
출력 방법은 System.out.println()을 사용했다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		List<String> list = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			String str = br.readLine();
			if (!list.contains(str)) list.add(str);
		}
		
		list.sort((s1, s2) -> {
			if (s1.length() == s2.length()) { // 1차 수정 테스트
				return s1.compareTo(s2);
			}
			return s1.length() - s2.length();
		});
		
		for(String s : list) System.out.println(s); 
	}
}

3번. 2차 수정코드

배열 종류는 ArrayList<String>을 사용했다.
비교 방법은 charAt() 비교를 사용했다.
출력 방법을 StringBuilder에 list의 요소를 넣고, System.out.println(sb.toString()) 으로 출력했다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		List<String> list = new ArrayList<>();
		for(int i = 0; i < n; i++) {
			String str = br.readLine();
			if (!list.contains(str)) list.add(str);
		}
		
		list.sort((s1, s2) -> {
			if (s1.length() != s2.length()) return s1.length() - s2.length();
			else {
				for (int i = 0; i < s1.length(); i++) {
				 if (s1.charAt(i) != s2.charAt(i)) 
					 return s1.charAt(i) - s2.charAt(i);
				}
			}
			return s1.length() - s2.length();
		});
		
		StringBuilder sb = new StringBuilder(); // 2차 수정 테스트
		for(String s : list) {
			sb.append(s+"\n");
		}
		System.out.println(sb.toString());
	}
}

4번. 3차 수정코드

배열 종류를 ArrayList<String> 에서 String 배열로 변경했다.
비교 방법은 charAt() 비교를 사용했다.
출력 방법은 StringBuilder에 list의 요소를 넣고, System.out.println(sb.toString()) 으로 출력했다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		String[] strArr = new String[n]; // 3차 수정 테스트
		for(int i = 0; i < n; i++) {
			strArr[i] = br.readLine();
		}
		
		Arrays.sort(strArr, ((s1, s2) -> { // 3차 수정 테스트
			if (s1.length() != s2.length()) return s1.length() - s2.length();
			else {
				for (int i = 0; i < s1.length(); i++) {
					if (s1.charAt(i) != s2.charAt(i)) return s1.charAt(i) - s2.charAt(i);
				}
			}
			return s1.length() - s2.length();
		}));
		
		StringBuilder sb = new StringBuilder();
		sb.append(strArr[0]+"\n"); // 3차 수정 테스트
		for(int i = 1; i < strArr.length; i++) {
			if(!strArr[i].equals(strArr[i-1])) {
				sb.append(strArr[i]+"\n");
			}
		}
		
		System.out.println(sb.toString());
	}
}

5번. 4차 수정코드

배열 종류는 String 배열을 사용했다.
비교 방법을 charAt() 비교에서 String.compareTo(s)로 바꿨다.
출력 방법은 StringBuilder에 list의 요소를 넣고, System.out.println(sb.toString()) 으로 출력했다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		String[] strArr = new String[n]; // 3차 수정 테스트
		for(int i = 0; i < n; i++) {
			strArr[i] = br.readLine();
		}
		
		Arrays.sort(strArr, ((s1, s2) -> { // 4차 수정 테스트
			if (s1.length() == s2.length()) return s1.compareTo(s2);
			return s1.length() - s2.length();
		}));
		
		StringBuilder sb = new StringBuilder();
		sb.append(strArr[0]+"\n"); // 3차 수정 테스트
		for(int i = 1; i < strArr.length; i++) {
			if(!strArr[i].equals(strArr[i-1])) {
				sb.append(strArr[i]+"\n");
			}
		}
		
		System.out.println(sb.toString());
	}
}

6번. 5차 수정코드

배열 종류는 String 배열을 사용했다.
비교 방법은 String.compareTo(s)를 사용했다.
출력 방법을 System.out.println(sb.toString())에서 BufferedWriter bw로 write(sb.toString)하는 것으로 바꿨다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 5차 수정 테스트
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
		
		String[] strArr = new String[n]; // 3차 수정 테스트
		for(int i = 0; i < n; i++) {
			strArr[i] = br.readLine();
		}
		
		Arrays.sort(strArr, ((s1, s2) -> { // 4차 수정 테스트
			if (s1.length() == s2.length()) return s1.compareTo(s2);
			return s1.length() - s2.length();
		}));
		
		StringBuilder sb = new StringBuilder();
		sb.append(strArr[0]+"\n"); // 3차 수정 테스트
		for(int i = 1; i < strArr.length; i++) {
			if(!strArr[i].equals(strArr[i-1])) {
				sb.append(strArr[i]+"\n");
			}
		}
		 bw.write(sb.toString()); // 5차 수정 테스트
		 
		 bw.flush();
		 bw.close();
		 br.close();
	}
}

7번. 6차 수정코드

배열 종류는 String 배열을 사용했다.
비교 방법은 String.compareTo(s)를 사용했다.
출력 방법을 br.write(sb.toString)에서 br.write(배열요소)로 바꿨다.

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 5차 수정 테스트
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
		
		String[] strArr = new String[n]; // 3차 수정 테스트
		for(int i = 0; i < n; i++) {
			strArr[i] = br.readLine();
		}
		
		Arrays.sort(strArr, ((s1, s2) -> { // 4차 수정 테스트
			if (s1.length() == s2.length()) return s1.compareTo(s2);
			return s1.length() - s2.length();
		}));
		
		bw.write(strArr[0]+"\n"); // 6차 수정 테스트
		for(int i = 1; i < strArr.length; i++) {
			if(!strArr[i].equals(strArr[i-1])) {
				 bw.write(strArr[i]+"\n"); // 6차 수정 테스트
			}
		}
		 
		 bw.flush();
		 bw.close();
		 br.close();
	}
}